package com.share.algorithm.sort;

/**
 * @desc: 插入排序
 * @author:caifan
 * @date:2020/9/24
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] arrays = new int[]{12, 4, 8, 7, 2, 10, 6, 9, 3, 5};
        insertSort(arrays);
    }

    /**
     * 插入排序，可以理解打扑克顺序插排
     *      第一个数据不需要比较
     *      每次插入的数据从后往前比较，如果找到比这个数据小的交换位置停止
     *      如果比它大结束
     * @param arrays
     * @return
     */
    public static int[] insertSort(int[] arrays) {
        //第一个数不用比较
        for (int i = 1; i < arrays.length; i++) {
            int data = arrays[i];
            int j = i - 1;
            for (;j >= 0;j--) {//从尾到头，前面是排好序的，找到比它小的就不用找了
                if (arrays[j] > data) {
                    arrays[j+1] = arrays[j];//数据往后移动
                } else {
                    break;//O(1)
                }
            }
            arrays[j+1] = data;

            System.out.println("第" + i + "次排序结果");
            for (j = 0; j < arrays.length; j++) {
                System.out.print(arrays[j] + " ");
            }
            System.out.println();
        }

        return arrays;
    }
}
